package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by 朱城委 on 2021/10/13.<br><br>
 *
 * 中等：字母异位词分组
 */
public class Topic49 {

    public static void main(String[] args) {
        Topic49 instance = new Topic49();

        String[] array = new String[] {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(instance.groupAnagrams(array));

        array = new String[] {};
        System.out.println(instance.groupAnagrams(array));

        array = new String[] {"a"};
        System.out.println(instance.groupAnagrams(array));

        array = new String[] {"ddddddddddg","dgggggggggg"};
        System.out.println(instance.groupAnagrams(array));
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = new char[26];
            for (char c : s.toCharArray()) ca[c - 'a']++;
            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<>());
            map.get(keyStr).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public List<List<String>> groupAnagrams3(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for(String value : strs) {
            byte[] count = new byte[26];
            for(char ch : value.toCharArray()) {
                count[ch - 'a']++;
            }

            StringBuilder builder = new StringBuilder();
            for(int i = 0; i < count.length; i++) {
                if(count[i] > 0) {
                    builder.append((char) ('a' + i));
                    builder.append(count[i]);
                }
            }

            String key = builder.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(value);
            map.put(key, list);
        }

        return new ArrayList<>(map.values());
    }

    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for(String value : strs) {
            char[] array = value.toCharArray();
            Arrays.sort(array);
            String key = String.valueOf(array);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(value);
            map.putIfAbsent(key, list);
        }

        return new ArrayList<>(map.values());
    }
}
